package com.gary;


import java.util.Arrays;

/**
 * @author peng_rui
 * @date 2022/7/23
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] arr = new int[]{3, 4, 9, 8, 4, 5, 1, 6};
//        int[] arr = new int[]{1,3,5,9,10,20};
////        quick(arr, 0, arr.length - 1);
//        popSort2(arr);
        popSort3(arr);
////        insertSort(arr);
        System.out.println(Arrays.toString(arr));
//        int idx = bSearch2(arr, 9);
//        System.out.println(idx);
    }

    public static void quick(int[] a, int l, int h) {
        if (l >= h) {
            return;
        }
        int p = partition(a, l, h);
        quick(a, l, p - 1);
        quick(a, p + 1, h);
    }

    public static int partition(int[] a, int l, int h) {
        int i = l;
        int j = h;
        int pv = a[l];
        while (i < j) {
            while (i < j && a[j] > pv) {
                j--;
            }
            while (i < j && a[i] <= pv) {
                i++;
            }
            int t = a[i];
            a[i] = a[j];
            a[j] = t;
        }
        int t = a[l];
        a[l] = a[j];
        a[j] = t;
        return j;
    }

    /**
     * 冒泡
     * @param a
     */
    public static void popSort(int[] a) {
        for (int i = 0; i < a.length - 1; i++) {
            boolean flag = true;
            for (int j = 0; j < a.length - i - 1; j++) {
                if (a[j] > a[j + 1]) {
                    swap(a, j, j+1);
                    flag = false;
                }
            }
            if (flag) {
                return;
            }
            System.out.println("第 [" + i + "]轮 " + Arrays.toString(a));
        }
    }

    /**
     * 插入排序
     * @param a
     */
    public static void insertSort(int[] a) {
        for (int i = 0; i < a.length - 1; i++) {
            int needChangeIdx = i;
            for (int j = i + 1; j < a.length; j++) {
                if (a[needChangeIdx] > a[j]) {
                    needChangeIdx = j;
                }
                System.out.println("第 [" + (j - i) + "]次比较 ");
            }
            if (i != needChangeIdx) {
                swap(a, i, needChangeIdx);
            }
            System.out.println("第 [" + i + "]轮 " + Arrays.toString(a));
        }
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void popSort2(int[] a) {
        for (int i = 0; i < a.length; i++) {
            boolean flag = true;
            for (int j = 0; j < a.length - i - 1; j++) {
                if (a[j] > a[j + 1]) {
                    swap(a, j, j+1);
                    flag = false;
                }
            }
            if (flag) {
                return;
            }
        }
    }


    public static void popSort3(int[] a) {
        for (int i = 0; i < a.length - 1; i++) {
            boolean flag = true;
            for (int j = 0; j < a.length - i - 1; j++) {
                if (a[j] > a[j + 1]) {
                    int temp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = temp;
                    flag = false;
                }
            }
            if (flag) {
                break;
            }
        }
    }

    public static int bSearch(int[] a, int target) {
        int left = 0;
        int right = a.length;
        int mid = left - (left - right) / 2;
        while (left < right) {
            if (a[mid] == target) {
                break;
            }
            if (a[mid] > target && left < right) {
                right = mid;
                mid = left - (left - right) / 2;

            }
            if (a[mid] < target && left < right) {
                left = mid;
                mid = left - (left - right) / 2;

            }
        }
        return mid;
    }

    public static int bSearch2(int[] a, int target) {
        int left = 0;
        int right = a.length;
        int mid = left - ((left - right) / 2);
        while (left < right) {
            if (target == a[mid]) {
                break;
            }
            if (target < a[mid] && left < right) {
                right = mid;
                mid = left - ((left - right) / 2);
            }
            if (target > a[mid] && left < right) {
                left = mid;
                mid = left - ((left - right) / 2);
            }
        }
        return mid;
    }
}
